Shen LI Yong JIANG Takeshi IKENAGA Satoshi GOTO
In adaptive motion estimation, spatial-temporal correlation based motion type inference has been recognized as an effective way to guide the motion estimation strategy adjustment according to video contents. However, the complexity and the reliability of those methods remain two crucial problems. In this paper, a motion vector field model is introduced as the basis for a new spatial-temporal correlation based motion type inference method. For each block, Full Search with Adaptive Search Window (ASW) and Three Step Search (TSS), as two search strategy candidates, can be employed alternatively. Simulation results show that the proposed method can constantly reduce the dynamic computational cost to as low as 3% to 4% of that of Full Search (FS), while remaining a closer approximation to FS in terms of visual quality than other fast algorithms for various video sequences. Due to its efficiency and reliability, this method is expected to be a favorable contribution to the mobile video communication where low power real-time video coding is necessary.
In the H.264 video coding standard, 7 modes {1616, 168, 816, 88, 84, 48, 44} are used to enhance the coding efficiency. The motion vector estimation with 7 modes may require huge computing time. Thus, several efficient ME schemes have been proposed to reduce the complexity of ME module in H.264. In this paper, we propose a ME scheme using a modified early termination technique to speed up the motion vector estimation procedure while maintaining high image quality. We demonstrate the effectiveness of the proposed method by computer simulation. In the simulation results, the CPU time consumed by the proposed scheme is much less than that of the conventional scheme while the encoded video quality remains unchanged. This is due to the fact that the proposed scheme searches MVs from the smallest block mode to the largest block mode, and utilizes the correlation between neighbor MVs. Furthermore, the process of the proposed ME scheme can bypass to the next mode when the MVs of a mode are highly correlated with each other, while the conventional schemes can not skip to other modes.
Dong-Noh KIM Ki-Hong KIM Tae-Yeon JUNG Duk-Gyoo KIM
The recent sight system requires high stabilization functions for the longer range of observation and the higher kill probability. To this end, it is necessary to compensate rotational disturbances which are not stabilized with the conventional 2-axes stabilization system. This paper proposes a simple method on the rotational motion estimation for the stabilization of the sight system.
A new algorithm for computing precise estimates of the motion vectors of moving objects in a sequence of images is presented. The proposed method is a fusion of block-matching motion estimation and global optimization technique. To avoid some contradictions between global optimization techniques and piece-wise smooth values of sought motion vectors, a hidden segmentation model is utilized. Computer simulation and experimental results demonstrate a good performance of the method in terms of dynamic motion analysis.
Junichi MIYAKOSHI Yuichiro MURACHI Koji HAMANO Tetsuro MATSUNO Masayuki MIYAMA Masahiko YOSHIMOTO
This paper proposes a low-power systolic array architecture for a block-matching motion estimation processor IP for portable and high-resolution video applications. The architecture features a ring-connected processing element (PE) array to reduce both computation cycles and memory access cycles at the same time, allowing lower power characteristics. The feature of low memory access cycles allows concurrent operation of a half-pel processing unit with no extra cache. Furthermore, the architecture allows various summation schemes for absolute difference values. For that reason, it is applicable to various video coding modes such as the adaptive field/frame mode in MPEG2 and multiple macroblock mode in H.264. When the architecture is introduced to a design of a MPEG2 MP@HL motion estimation processor VLSI, the power consumption of the VLSI is reduced by 45-73% in comparison to cases with conventional architectures for motion estimation.
Xiaoying GAN Shiying SUN Wentao SONG Bo LIU
A novel threshold choosing method for the threshold-based skip mechanism is presented, in which the threshold is obtained from the analysis of the video device induced noise variance. Simulation results show that the proposed method can remarkably reduce the computation time consumption with only marginal performance penalty.
The rate-distortion optimization (RDO) method is an informative technology that improves the coding efficiency, but increases the computational complexity, of the H.264 encoder. In this letter, a fast Macroblock mode determination algorithm is proposed to reduce the computational complexity of the H.264 encoder. The proposed method reduces the encoder complexity by 55%, while maintaining the same level of coding efficiency.
Won-Gi HONG Young-Ro KIM Tae-Myoung OH Sung-Jea KO
Recently, many algorithms have been proposed for fast full search motion estimation. Among them, successive elimination algorithm (SEA) and its modified algorithms significantly speed up the performance of the full search algorithm. By introducing the inequality equation between the norm and the mean absolute difference (MAD) of two matching blocks, the SEA can successively eliminate invalid candidate blocks without any loss in estimation accuracy. In this paper, we propose a partial norm based early rejection algorithm (PNERA) for fast block motion estimation. The proposed algorithm employs the sum of partial norms from several subblocks of the block. Applying the sum of partial norms to the inequality equation, we can significantly reduce the computational complexity of the full search algorithm. In an attempt to reduce the computational load further, the modified algorithms using partial norm distortion elimination (PNDE) and subsampling methods are also proposed. Experimental results show that the proposed algorithm is about 4 to 9 times faster than the original exhaustive full search, and is about 3 to 4 times faster than the SEA.
Jin-Woo BAE Seung-Hyun LEE Ji-Sang YOO
In this paper, we propose a wavelet-based fast motion estimation algorithm for video sequence encoding with a low bit-rate. By using one of the properties of wavelet transform, multi-resolution analysis (MRA), and the spatial interpolation of an image, we can simultaneously reduce the prediction error and the computational complexity inherent in video sequence encoding. In addition, by defining a significant block (SB) based on the differential information of wavelet coefficients between successive frames, the proposed algorithm enables us to make up for the increase in the number of motion vectors when the MRME algorithm is used. As a result, we are not only able to improve the peak signal-to-noise ratio (PSNR), but also reduce the computational complexity by up to 67%.
Ching-Ting HSU Hung-Ju LI Mei-Juan CHEN
The three main reasons why the new H.264 (MPEG-4 AVC) video coding standard has a significant performance better than the other standards are the adoption of variable block sizes, multiple reference frames, and the consideration of rate distortion optimization within the codec. However, these features incur a considerable increase in encoder complexity. As for the multiple reference frames motion estimation, the increased computation is in proportion to the number of searched reference frames. In this paper, a fast multi-frame selection method is proposed for H.264 video coding. The proposed scheme can efficiently determine the best reference frame from the allowed five reference frames. Simulation results show that the speed of the proposed method is over two times faster than that of the original scheme adopted in JVT reference software JM73 while keeping the similar video quality and bit-rate.
Yung-Lyul LEE Yung-Ki LEE HyunWook PARK
A fast motion estimation algorithm is proposed, which performs a tree-structured motion vector search for variable blocks in the integer-pixel unit. The proposed method is based on the inequality of sum norms to find the best estimate of the motion vectors for variable blocks. The proposed motion estimation algorithm is applied to the Joint Video Team (JVT) encoder that performs variable-block motion estimation (ME) with quarter-pixel unit. In terms of computational complexity, the proposed motion estimation algorithm searches motion vectors about 10.7 times as fast as the spiral full search with early termination and 6.6 times as fast as the fast full search using the hierarchical sum of absolute difference (SAD), while the PSNR (peak signal-to-noise ratio) of the reconstructed image is slightly degraded.
Jen-Yi HUANG Lung-Jen WANG Hsi-Han CHEN Sheng-Li WEI Wen-Shyong HSIEH
Motion estimation is the key issue in video compressing. Several methods for motion estimation based on the center biased strategy and minimum mean square error trend searching have been proposed, such as TSS, FSS, UCBDS and MIBAS, but these methods yield poor estimates or find local minima. Many other methods predict the starting point for the estimation; such methods include PMEA, PSA and GPS: these can be fast but are inaccurate. This study addresses the causes of wrong estimates, local minima and incorrect predictions in the prior estimation methods. The Multiple Searching Trend (MST) is proposed to overcome the problems of ineffective searches and local minima, and the Adaptive Dilated Searching Field (ADSF) is described to prevent prediction from wrong location. Applying MST and ADSF to the listed estimating methods, such as UCBDS, a fast and accurate can be reached. For this this reason, the method is called CockTail Searching (CTS).
Bit-errors in a subband of a wavelet-based video frame during network transmission affect not only lower-level subbands within the same frame but also the subsequent frames. This is because the video frame is wavelet-transformed image with multi-levels and referenced from later frames. In this paper, we propose a new motion estimation scheme for wavelet-based video called Intra-frame Motion Estimation (IME), in which each subband except the LL subband refers to the 1-level-lower subband in the same orientation within the same frame. This scheme protects video quality by confining the effects of the bit-errors of all subbands, except the LL subband, within a frame. We evaluated the performance of our proposed scheme in a simulated wireless network environment. As a result of tests, it was shown that the proposed IME algorithm performs better than MRME, a motion-compensated video coding scheme for wavelet video, in a heavy motion video sequence, while IME outperforms MRME at a high bit-rate in small motion video sequence.
Sang Ju PARK Hyoung-Jin KIM Min Chul PARK
Modern video compression usually consists of ME/MC (Motion Estimation/Motion Compensation), transform, and quantization of the transform coefficients. Efficient bit allocation technique to distribute available bits to motion parameters and quantized coefficients is an important part of the whole system. A method that is very complex and/or needs buffering of many future frames is not suitable for real time application. We develop an efficient bit allocation technique that utilizes the estimated effect of allocated bits to motion parameter and quantization on the overall quality. We also propose an hierarchical block based ME/MC technique that requires less computations than classical BMA (Block Matching Algorithm) while offering better motion estimation.
Masayuki MIYAMA Junichi MIYAKOSHI Kousuke IMAMURA Hideo HASHIMOTO Masahiko YOSHIMOTO
This paper describes a VLSI-oriented motion estimation algorithm using a steepest descent method (SDM) applied to MPEG-4 visual communication with a mobile terminal. The SDM algorithm is optimized for QCIF or CIF resolution video and VLSI implementation. The SDM combined with a subblock search method is developed to enhance picture quality. Simulation results show that a mean PSNR drop of the SDM algorithm processing QCIF 15 fps resolution video in comparison with a full search algorithm is -0.17 dB. Power consumption of a VLSI based on the SDM algorithm assuming 0.18 µm CMOS technology is estimated at 2 mW. The VLSI attains higher picture quality than that based on the other fast motion estimation algorithm, and is applicable to mobile video applications.
Yung-Lyul LEE Hyun JO Ki-Hun HAN
Two fast quarter-pixel motion estimation algorithms using the integer motion vector (MV) already obtained by any fast motion estimation algorithm are proposed, which perform MV search only in half-pixel and quarter-pixel unit. The proposed algorithms search MV about 4-9 times as fast as the full search in quarter-pixel unit, while the PSNR is slightly degraded.
Kazutoshi KOBAYASHI Ryuta NAKANISHI Hidetoshi ONODERA
We propose an efficient motion estimation algorithm to search an additional area according to the motion of a camcorder, which is obtained from a gyro sensor. When the camcorder moves, the background moves in the opposite direction. The proposed algorithm searches three regions, one around the center, another around the predicted region and another in the background around the region associated with the camcorder motion. Compared to conventional algorithms without the last region, the proposed one reduces the amount of computation to 1/5 while maintaining or enhancing the quality.
Vasily G. MOSHNYAGA Koichi MASUNAGA
A new algorithm and architecture to eliminate redundant operations in block-matching (BM) motion estimation is proposed. The key step of this work is to use binary-matching to define image regions with the static background content and then exclude these regions from the actual motion estimation. According to experiments, the approach maintains the highest PSNR, while making as half as less computations in comparison to the adaptive BM or 1/8 of the computations required by the full-search BM. An implementation scheme is outlined.
Yankang WANG Makoto ANDO Tomohiro TANIKAWA Kazuhiro YOSHIDA Jun YAMASHITA Hideaki KUZUOKA Michitaka HIROSE
This paper presents a block-based motion vector search algorithm for video coding based on an interpolation scheme of search blocks. The basic idea of motion vector estimation between frames is to select a block in the previous frame that best matches a block in the current frame by minimizing the difference between them. In most of the search algorithms, however, the best-match block can only be on a pre-defined grid pattern. Although using a pre-defined pattern increases the search efficiency, it may also reduce the search accuracy. To balance the two aspects and to fully utilize the block information, we propose a strategy, which, instead of selecting from pre-defined blocks, searches for a best match interpolated from the pre-defined blocks. Experiment results demonstrate a better accuracy and efficiency of this search method than some commonly-used methods for different kinds of motion.
Kwan-Yee Kenneth WONG Roberto CIPOLLA
This paper presents a novel technique for reconstructing an outdoor sculpture from an uncalibrated image sequence acquired around it using a hand-held camera. The technique introduced here uses only the silhouettes of the sculpture for both motion estimation and model reconstruction, and no corner detection nor matching is necessary. This is very important as most sculptures are composed of smooth textureless surfaces, and hence their silhouettes are very often the only information available from their images. Besides, as opposed to previous works, the proposed technique does not require the camera motion to be perfectly circular (e.g., turntable sequence). It employs an image rectification step before the motion estimation step to obtain a rough estimate of the camera motion which is only approximately circular. A refinement process is then applied to obtain the true general motion of the camera. This allows the technique to handle large outdoor sculptures which cannot be rotated on a turntable, making it much more practical and flexible.